#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
      if(!root)  return false;
      stack<pair<TreeNode *, int>> st;
      st.push({root, root->val});
      while(!st.empty()){
        pair<TreeNode *, int> node = st.top();
        st.pop();

        if(!node.first->left && !node.first->right && node.second == targetSum) return true;

        if(node.first->right) st.push({node.first->right, node.second + node.first->right->val});
        if(node.first->left) st.push({node.first->left, node.second + node.first->left->val});
      }
      return false;
    }
};


// class Solution {
// private:
//     bool traversal(TreeNode* cur, int count) {
//         if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
//         if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回

//         if (cur->left) { // 左
//             count -= cur->left->val; // 递归，处理节点;
//             if (traversal(cur->left, count)) return true;
//             count += cur->left->val; // 回溯，撤销处理结果
//         }
//         if (cur->right) { // 右
//             count -= cur->right->val; // 递归，处理节点;
//             if (traversal(cur->right, count)) return true;
//             count += cur->right->val; // 回溯，撤销处理结果
//         }
//         return false;
//     }

// public:
//     bool hasPathSum(TreeNode* root, int sum) {
//         if (root == NULL) return false;
//         return traversal(root, sum - root->val);
//     }
// };


// 简单写法
// bool hasPathSum(TreeNode* root, int targetSum) {
//     if(!root) return false;
//     if(!root->left && !root->right && targetSum == root->val) return true;

//     return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
// }